package com.example.find;

import java.util.*;

/**
 * @author zhy
 * @version 1.0.0
 * @ClassName TopKFrequencySolution.java
 * @Description TODO
 * @createTime 2020年12月29日 15:39:00
 */
public class TopKFrequencySolution {

    /**
     * 描述
     * 给一个单词列表，求出这个列表中出现频次最高的K个单词。
     *
     * 你需要按照单词的词频排序后输出，越高频的词排在越前面。如果两个单词出现的次数相同，则词典序小的排在前面。
     *
     * 样例
     * 给出单词列表：
     *
     * [
     *     "yes", "lint", "code",
     *     "yes", "code", "baby",
     *     "you", "baby", "chrome",
     *     "safari", "lint", "code",
     *     "body", "lint", "code"
     * ]
     *
     * 如果 k = 3, 返回 [“code”, “lint”, “baby”]。
     * 如果 k = 4, 返回 [“code”, “lint”, “baby”, “yes”]。
     */
    public static List<String> topKFrequentWords(String[] words, int k) {
        List<String> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        int length = words.length;
        for (int i = 0; i < length; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>((x1, x2) -> {
            if (x1.getValue() < x2.getValue()) {
                return 1;
            } else if (x1.getValue() > x2.getValue()) {
                return -1;
            } else {
                return x1.getKey().compareTo(x2.getKey());
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            queue.add(entry);
        }

        for (int i = 0; i < k; i++) {
            String tmp = queue.peek().getKey();
            list.add(tmp);
            queue.poll();
        }
        return list;
    }




    public static void main(String[] args) {
        String[] strs = new String[]{"yes", "lint", "code",
                "yes", "code", "baby",
                "you", "baby", "chrome",
                "safari", "lint", "code",
                "body", "lint", "code"};
        List<String> list = topKFrequentWords(strs, 4);
        list.forEach(i -> System.out.println(i));

    }

}
